import java.util.ArrayList;
import java.util.List;

public class L257 {

    class Solution {
        public List<String> binaryTreePaths(TreeNode root) {

            ArrayList<String> result = new ArrayList<>();
            ArrayList<Integer> road = new ArrayList<>();

            dfs(root, road, result);

            return result;
        }

        private void dfs(TreeNode root, ArrayList<Integer> road, ArrayList<String> result) {
            if (root == null) {
                return;
            }
            road.add(root.val);
            if (root.left == null && root.right == null) {
                StringBuilder builder = new StringBuilder();
                for (int i = 0; i < road.size() - 1; i++) {
                    builder.append(road.get(i));
                    builder.append("->");
                }
                builder.append(road.get(road.size() - 1));
                result.add(builder.toString());
                return;
            }
            if (root.left != null) {
                dfs(root.left, road, result);
                road.remove(road.size() - 1);
            }
            if (root.right != null) {
                dfs(root.right, road, result);
                road.remove(road.size() - 1);
            }
        }
    }
}
